package org.usmile.algorithms.learn.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 希尔排序
 * <p>
 * 希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。
 * 希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，
 * 但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。
 */
public class ShellSorter {
    // 原地、不稳定
    public void sort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        for (int gap = nums.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < nums.length; i++) {
                int j = i;
                int temp = nums[i];
                for (; j >= gap; j -= gap) {
                    if (temp < nums[j - gap]) {
                        nums[j] = nums[j - gap];
                    } else {
                        break;
                    }
                }

                nums[j] = temp;
            }
        }
    }

    public void sort1(int[] data) {
        if (data == null || data.length <= 1) return;

        // 1. 计算递增序列
        int n = data.length;
        ArrayList<Integer> list = new ArrayList<>();
        int k = 1;
        int h;
        do {
            h = ((int) Math.pow(3, k) - 1) / 2;
            // bug 修复：需要考虑 n < 3 的场景，
            // 当 n < 3 的时候，不应该 break，而应该将 h 添加到 list 中
            if (h > n / 3 && n >= 3) break;
            list.add(h); // 1, 4, 13, 40, 121......
            k++;
        } while (h <= n / 3);

        // 2. 希尔排序
        for (k = list.size() - 1; k >= 0; k--) { // 倒序遍历
            h = list.get(k);
            // 将数组变为 h 有序
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h; j = j - h) {
                    if (data[j] < data[j - h]) {
                        int temp = data[j - h];
                        data[j - h] = data[j];
                        data[j] = temp;
                    } else {
                        break;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 4, 3, 2};
        new ShellSorter().sort(nums);

        System.out.println(Arrays.toString(nums));
    }
}
